package com.wandian.util;

/**
 * @author long
 * @Create 2012-10-4 上午10:54:21
 * @QQ 108232706
 * @version 1.0
 */
public class HashMap<K, V> {

	// transient
	static class Entry<K, V> {
		// final K key;
		K key;
		V value;
		Entry<K, V> next;
		// final int hash;
		int hash;

		Entry() {
			// value = -1;
			// next = null;
			// key = n;
			// hash = h;
		}

		/**
		 * Creates new entry.
		 */
		Entry(int h, K k, V v, Entry<K, V> n) {
			value = v;
			next = n;
			key = k;
			hash = h;
		}

		public final K getKey() {
			return key;
		}

		public final V getValue() {
			return value;
		}

		void recordAccess(HashMap<K, V> m) {
		}

		void recordRemoval(HashMap<K, V> m) {
		}

		public final void setEntry(int h, K k, V v, Entry<K, V> n) {
			value = v;
			next = n;
			key = k;
			hash = h;
		}

		public final V setValue(V newValue) {
			V oldValue = value;
			value = newValue;
			return oldValue;
		}

		@Override
		public final String toString() {
			return getKey() + "=" + getValue();
		}
	}

	static final int MAXIMUM_CAPACITY = 1 << 30;
	static final int DEFAULT_INITIAL_CAPACITY = 16;
	static final float DEFAULT_LOAD_FACTOR = 0.75f;

	/**
	 * 取莫前的数字
	 * 
	 * @param key
	 * @param h
	 * @return
	 */
	static int hash(Object key, int h, boolean canExpand) {
		if (canExpand) {
			if (key instanceof Integer) {
				return Integer.valueOf(key.toString());
			}
			if (key instanceof String) {
				// 获得"+this.mapName+"ascii码和
				int hash = 0;
				for (int i = 0; i < key.toString().length(); i++) {
					hash += key.toString().charAt(i);
				}
				return hash;
			}
		}

		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/**
	 * Returns index for hash code h.
	 */
	static int indexFor(Object key, int h, int length, boolean canExpand) {
		if (canExpand && (key instanceof Integer || key instanceof String)) {
			return h % length;
		}
		return h & (length - 1);
	}

	transient int size;
	int threshold;
	final float loadFactor;
	transient volatile int modCount;

	private static HashMap<String, String> instance = null;

	public synchronized static HashMap<String, String> getInstance() {

		if (instance == null) {
			instance = new HashMap<String, String>();
		}
		return instance;
	}

	private String mapName;

	transient Entry[] table;

	// private List<Entry> freelist;
	private boolean canExpand;

	public HashMap() {
		this("", DEFAULT_INITIAL_CAPACITY, (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR), true);
		// this.loadFactor = DEFAULT_LOAD_FACTOR;
		// threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
		// table = new Entry[DEFAULT_INITIAL_CAPACITY];
		// init();
	}

	public HashMap(String _mapName) {
		this(_mapName, DEFAULT_INITIAL_CAPACITY, (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR), true);
	}

	/**
	 * @param _mapName
	 *            哈希表名
	 * @param initialCapacity
	 *            table的长度
	 * @param _threshold
	 *            可容纳数据的长度
	 */
	public HashMap(String _mapName, int initialCapacity, int _threshold, boolean _canExpand) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: "
					+ initialCapacity);
		if (_threshold < 0)
			throw new IllegalArgumentException("Illegal initial _threshold: "
					+ initialCapacity);
		if (initialCapacity > MAXIMUM_CAPACITY)
			initialCapacity = MAXIMUM_CAPACITY;
		mapName = _mapName;
		canExpand = _canExpand;
		// int capacity = 1;
		// while (capacity < initialCapacity)
		// capacity <<= 1;
		threshold = _threshold;// (int) (capacity * loadFactor);
		this.loadFactor = threshold / initialCapacity;
		table = new Entry[initialCapacity];
		init();
	}

	boolean addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		// 取空闲的v
		// Entry<K, V> tempEntry = freelist.get(0);
		// if (tempEntry == null)
		// return false;
		// tempEntry.setEntry(hash, key, value, e);
		// new Entry<K, V>(hash, key,value, e);在资源里找到引用，并通过引用操作指向的数据
		table[bucketIndex] = new Entry<K, V>(hash, key, value, e);// tempEntry;//
																	// freelist.get(0);
		// freelist.remove(tempEntry);
		if (size++ >= threshold && canExpand)
			resize(2 * table.length);
		return true;
	}

	public void clear() {
		synchronized (this) {
			modCount++;
			Entry[] tab = table;
			for (int i = 0; i < tab.length; i++) {
				// for (Entry<K, V> e = table[i]; e != null; e = e.next) {
				// freelist.add(e);// 如果null
				// }
				tab[i] = null;
			}
			// System.out.println("clear后，freelist长度为：" + freelist.size());
			size = 0;
		}

	}

	public boolean containsKey(Object key) {
		synchronized (this) {
			return getEntry(key) != null;
		}

	}

	private boolean containsNullValue() {
		Entry[] tab = table;
		for (int i = 0; i < tab.length; i++)
			for (Entry e = tab[i]; e != null; e = e.next)
				if (e.value == null)
					return true;
		return false;
	}

	public boolean containsValue(Object value) {
		synchronized (this) {
			if (value == null)
				return containsNullValue();

			Entry[] tab = table;
			for (int i = 0; i < tab.length; i++)
				for (Entry e = tab[i]; e != null; e = e.next)
					if (value.equals(e.value))
						return true;
			return false;
		}

	}

	public V get(Object key) {
		synchronized (this) {
			String threadName = Thread.currentThread().getName();
			// System.out.println(threadName + ",《获得" + this.mapName + "get（k "
			// + key + "）锁！k:" + key);
			if (key == null) {
				// System.out.println(threadName + ",释放" + this.mapName +
				// "get（k "
				// + key + "）锁！》");
				return getForNullKey();
			}
			int hash = hash(key, key.hashCode(), canExpand);
			int index = indexFor(key, hash, table.length, canExpand);
			// System.out.println(key.getClass().getName() + ":" + key +
			// " hash:" + hash + " in hash table link index " + index);
			for (Entry<K, V> e = table[index]; e != null; e = e.next) {
				Object k;
				if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
					// System.out.println(threadName + ",释放" + this.mapName
					// + "get（k " + key + "）锁！》");
					return e.value;
				}
			}
			// System.out.println(threadName + ",释放" + this.mapName + "get（k "
			// + key + "）锁！》");
			return null;
		}

	}

	final Entry<K, V> getEntry(Object key) {
		int hash = (key == null) ? 0 : hash(key, key.hashCode(), canExpand);
		for (Entry<K, V> e = table[indexFor(key, hash, table.length, canExpand)]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash
					&& ((k = e.key) == key || (key != null && key.equals(k))))
				return e;
		}
		return null;
	}

	private V getForNullKey() {
		for (Entry<K, V> e = table[0]; e != null; e = e.next) {
			if (e.key == null)
				return e.value;
		}
		return null;
	}

	public String getMapName() {
		return mapName;
	}

	/**
	 * 初始化资源内存，在系统初始化时候一次性申请好
	 */
	void init() {
		// freelist = new ArrayList<Entry>();
		// for (int i = 0; i < threshold; i++) {
		// freelist.add(new Entry<K, V>(0, null, null, null));
		// }
	}

	public boolean isEmpty() {
		synchronized (this) {
			return size == 0;
		}

	}

	// public boolean isFreelistCorect() {
	// synchronized (this) {
	// return freelist.size() + size == threshold;
	// }
	//
	// }

	public boolean put(K key, V value) {
		synchronized (this) {
			String threadName = Thread.currentThread().getName();
			// System.out.println(threadName + "《获得" + this.mapName + "put（k"
			// + key + "，v" + value + "）锁");
			if (!canExpand && size >= threshold) {
				System.out.println(this.getMapName() + "容量已满:" + threshold);
				return false;
			}
			if (key == null) {
				boolean flag = putForNullKey(value);
				// System.out.println(threadName + ",释放" + this.mapName +
				// "put（k"
				// + key + "，v" + value + "）锁！》");
				return flag;
			}

			int hash = hash(key, key.hashCode(), canExpand);
			int i = indexFor(key, hash, table.length, canExpand);
			// System.out.println(key.getClass().getName() + ":" + key +
			// " hash:"
			// + hash + " in hash table link index " + i);
			for (Entry<K, V> e = table[i]; e != null; e = e.next) {
				Object k;
				if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
					// V oldValue = e.value;
					// e.value = value;
					// e.recordAccess(this);
					// System.out.println(threadName + ",释放" + this.mapName
					// + "put （k" + key + "，v" + value + "）锁！》");
					return false;
				}
			}

			modCount++;
			addEntry(hash, key, value, i);
			// System.out.println(threadName + ",释放" + this.mapName + "put（k"
			// + key + "，v" + value + "）锁！》");
			return true;
		}

	}

	private boolean putForNullKey(V value) {
		for (Entry<K, V> e = table[0]; e != null; e = e.next) {
			if (e.key == null) {
				// V oldValue = e.value;
				// e.value = value;
				// e.recordAccess(this);
				return false;
			}
		}
		modCount++;
		addEntry(0, null, value, 0);
		return true;
	}

	public boolean remove(Object key) {
		synchronized (this) {
			Entry<K, V> e = removeEntryForKey(key);
			// if (e != null)
			// freelist.add(e);
			return (e == null ? false : true);
		}

	}

	final Entry<K, V> removeEntryForKey(Object key) {
		int hash = (key == null) ? 0 : hash(key, key.hashCode(), canExpand);
		int i = indexFor(key, hash, table.length, canExpand);
		Entry<K, V> prev = table[i];
		Entry<K, V> e = prev;

		while (e != null) {
			Entry<K, V> next = e.next;
			Object k;
			if (e.hash == hash
					&& ((k = e.key) == key || (key != null && key.equals(k)))) {
				modCount++;
				size--;
				if (prev == e)
					table[i] = next;
				else
					prev.next = next;
				e.recordRemoval(this);
				return e;
			}
			prev = e;
			e = next;
		}

		return e;
	}

	void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}

		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

	public void setMapName(String mapName) {
		this.mapName = mapName;
	}

	public int size() {
		synchronized (this) {
			return size;
		}

	}

	void transfer(Entry[] newTable) {
		Entry[] src = table;
		int newCapacity = newTable.length;
		for (int j = 0; j < src.length; j++) {
			Entry<K, V> e = src[j];
			if (e != null) {
				src[j] = null;
				do {
					Entry<K, V> next = e.next;
					int i = indexFor(e.key, e.hash, newCapacity, canExpand);
					e.next = newTable[i];
					newTable[i] = e;
					e = next;
				} while (e != null);
			}
		}
	}

	public boolean update(K key, V value) {
		synchronized (this) {
			String threadName = Thread.currentThread().getName();
			// System.out.println(threadName + "《获得" + this.mapName +
			// "update（k "
			// + key + "，v " + value + "）锁");
			if (key == null) {
				boolean flag = updateForNullKey(value);
				// System.out.println(threadName + ",释放" + this.mapName
				// + "update（k " + key + "，v " + value + "）锁！》");
				return flag;
			}

			int hash = hash(key, key.hashCode(), canExpand);
			int i = indexFor(key, hash, table.length, canExpand);
			for (Entry<K, V> e = table[i]; e != null; e = e.next) {
				Object k;
				if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
					// V oldValue = e.value;
					e.value = value;
					e.recordAccess(this);
					// System.out.println(threadName + ",释放" + this.mapName
					// + "update（k " + key + "，v " + value + "）锁！》");
					return true;
				}
			}
			// System.out.println(threadName + ",释放" + this.mapName +
			// "update（k "
			// + key + "，v " + value + "）锁！》");
			return false;
		}

	}

	private boolean updateForNullKey(V value) {
		for (Entry<K, V> e = table[0]; e != null; e = e.next) {
			if (e.key == null) {
				// V oldValue = e.value;
				e.value = value;
				e.recordAccess(this);
				return true;
			}
		}
		return false;
	}

}
